//
// Description: 312. 戳气球
// Created by Loading on 2022/6/17.
//

#include <bits/stdc++.h>

using namespace std;

int maxCoins(vector<int> &nums) {
    int n = nums.size();
    if (n == 1) {
        return nums[0];
    }

    // 为状态转移方便，构建新数组，前后添加 1
    vector<int> vec(n + 2);
    vec[0] = vec[n + 1] = 1;
    for (int i = 0; i < n; ++i) {
        vec[i + 1] = nums[i];
    }

    /* 区间dp */
    // dp[i][j] 表示区间 [i,j] 获得的最大硬币
    int dp[n + 2][n + 2];
    memset(dp, 0, sizeof dp);

    // 枚举区间长度
    for (int len = 1; len <= n; ++len) {
        // 枚举起始位置
        for (int i = 1; i + len - 1 < n + 1; ++i) {
            int j = i + len - 1;
            // 枚举起始位置到结束位置的每一个点，作为最后戳破的气球
            for (int k = i; k <= j; ++k) {
                // 左侧最大硬币 + 右侧最大硬币 + 最后戳破时获得的硬币
                int cnt = dp[i][k - 1] + dp[k + 1][j] + vec[i - 1] * vec[k] * vec[j + 1];
                // 更新 dp 数组
                dp[i][j] = max(dp[i][j], cnt);
            }
        }
    }

    return dp[1][n];
}

int main() {
    vector<int> nums{3, 1, 5, 8};

    auto res = maxCoins(nums);

    cout << res << endl;

    return 0;
}